package com.caoyanan.algorithm.question.zuoTraining.training004.class04;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 约瑟夫环问题
 *
 * 给一个环形单链表，链表长度为N，给一个数k，从头结点开始(算是第1个数)，转到第k个数，移除节点，然后再接着转到第k个数，移除节点，求最后剩下的那个节点是什么
 * @author: caoyanan
 * @time: 2021/6/20 12:31
 */
public class Question02_JosephRing {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }

    }


    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = head;

        int count = 100000;
        for (int i = 8; i <= count; i++) {
            int order = violentJosephKill(head, i);
            int order2 = functionJosephKill(head, i);
            if (order != order2) {
                System.out.printf("数到 %s 杀人，暴力方法最后活的人编号是 %s, 约瑟夫环公式最后活的人编号是 %s \n",
                        i, order, order2);
            }

        }

    }

    /**
     * 公式求约瑟夫环 O(n)
     * 首先，需要知道谁报k数， 比如m个人，从1开始报数，几号报k数
     * 就比如5个人，依次从1开始报数，报数是7的是几号， 可以发现2号报7
     *  函数为 报k数的人序号 = ( k - 1 ) % 人数 + 1    (从最简单的 y = x % i,然后y是上加下减，x左加右减变换而来)
     *
     * 然后再看，目前是i号的人，在上一轮的旧编号是多少号，即 旧编号 = f(新编号) 的 函数是什么
     *  还是从例子入手， 比如5个人 1，2，3，4，5。依次报号然后报到7杀掉了，
     *      剩下的人编号为       4，×，1，2，3    而且，新编号和旧编号之间也肯定和k有关系
     *  通过尝试，发现 旧编号 = (新编号 + k -1) % 人数 + 1 ，例如 1 = (4 + 7 -1) % 5 + 1， 3 = (1 + 7 - 1) % 5 + 1
     *
     *
     * @param head
     * @param k
     * @return
     */
    private static int functionJosephKill(Node head, int k) {

        int length = 0;
        Node current = head;
        Set<Node> set = new HashSet<>();
        while (current != null && !set.contains(current)) {
            current = current.next;
            set.add(current);
            length++;
        }

        int number = 1;
        // 求第 length -1 次之前的编号是多少
        for (int i = 1; i <= length - 1; i++) {
            number = (number + k - 1) % length + 1;
        }
        return number;
    }

    /**
     * 给一个环形链表 1->2->3->4->5……>1   数到k就杀人，求最后活着的人是几号
     * 暴力方法，时间复杂度O(n*k)
     * @param head
     * @param k
     */
    private static int violentJosephKill(Node head, int k) {
        Map<Node, Integer> order = new HashMap<>();
        Node node = head;
        int i = 1;
        while (node != null && !order.containsKey(node)) {
            order.put(node, i++);
            node = node.next;
        }
        node = head;
        while (order.size() > 1) {
            i = 1;
            // 当前node就是要被删的节点
            while (i < k) {
                node = node.next;
                i++;
            }
            Node preNode = findPrevNode(head, node);
            preNode.next = node.next;
            if (node == head) {
                head = node.next;
            }
            node.next = null;
            order.remove(node);
            node = preNode.next;
        }
        Integer[] orders = order.values().toArray(new Integer[]{});
        return orders[0];
    }

    private static Node findPrevNode(Node head, Node node) {

        Node current = head;
        while (current.next != node) {
            current = current.next;
        }
        return current;
    }
}
